package org.example.sward.tooffer;

import java.util.Map;

/**
 * <p>
 * Description:
 * <p>
 * Copyright: 天津联想协同科技有限公司
 * <p>
 * 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
 * 输入: [7,1,5,3,6,4]
 * 输出: 5
 * 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
 *      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
 * @author anlu
 * @date 2022/2/11 15:15
 */
public class Offer63 {

    /**
     * dp[i]=max(dp[i−1],prices[i]−min(prices[0:i]))
     * 前i日最大利润=max(前(i−1)日最大利润,第i日价格−前i日最低价格)
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int cost = Integer.MAX_VALUE,profix = 0;
        for (int price:prices){
            cost = Math.min(cost,price);
            profix = Math.max(profix,price - cost);
        }
        return profix;
    }

    public static void main(String[] args) {
        Offer63 offer = new Offer63();
        int[] array = new int[]{7,1,5,3,6,4};
        int result = offer.maxProfit(array);
        System.out.println(result);
    }

}
